/**
 * 给定一个整数sum，从有N个有序元素的数组中寻找元素a，b，
 * 使得a+b的结果最接近sum，
 * 最快的平均时间复杂度是
 */

/**
 * 答案解析：
 *
 * 此题目中，数组元素有序，
 * 所以a,b两个数可以分别从开始和结尾处开始搜，
 * 根据首尾元素的和是否大于sum,决定搜索的移动，整个数组被搜索一遍，
 * 就可以得到结果，所以最好时间复杂度为n
 */
public class Test6 {
    public static void main(String[] args) {
        int[] sum = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        //注意，题目说明了是有序数组
        //System.out.println(sumNearest(sum, 5).toString());
        int[] sum1 =sumNearest(sum, 5);
        for(int num:sum1){

            System.out.println(num);
        }



    }
    public static int[] sumNearest(int[] arr,int k) {//返回最近的两个元素的下标（以数组的形式）

        int i = 0;
        int j = arr.length - 1;
        while (i < j) {

            int num = arr[i] + arr[j];
            if(num < k) {
                i++;
            }else if(num > k) {
                j--;
            }else{
                return new int[]{arr[i], arr[j]};
            }//能走到这里，说明，是等于了，找到了最近的，是相等的，所以直接返回

        }
        //能走到这里，说明已经将数组遍历过了，此时是没有相等，但最合适的—>时间复杂度O(N)
        return new int[]{arr[i], arr[j]};

    }
}
